Generic programming with combinators and objects

Kosarev D.S., Boulytchev D.Yu. Generic programming with combinators and objects. Scientific and Technical Journal of Information Technologies, Mechanics and Optics, 2021, vol. 21, no. 5, pp. 720–726 (in Russian). doi: 10.17586/2226-1494-2021-21-5-720-726

The generic programming approach is popular in functional languages (for example, OCaml, Haskell). In essence, it is a compile-time generation of code that performs transformations of user-defined data types. The generated code can carry out various kinds of transformations of the values. Usually, transformations are represented as functions that implement algorithms of transformation. New transformations could be built from these transformation functions and user-defined ones. The representation based on functions has a downside: functions behave as final representations, and hence it is not possible to modify the behavior of the already built function. If the current set of transformations does not suit well, software developers are obliged to write a completely distinct transformation, even in the case when the new transformation is almost identical to the existing one. This work proposes to build transformations that are extensible after construction. The object-oriented programming paradigm will be followed, transformations will be represented not as functions but as objects. Instead of calling a transformation function, one of the object’s methods will be called. The transformation itself will be split into methods. The extensibility is supported by adding new methods and overriding existing ones. In this paper, the authors propose an approach to represent transformations as objects in the OCaml functional programming language. Every alternative in data type definition has a corresponding object method. This design allows the construction of many distinct transformations. The cases where too many methods are not desirable are also discussed. The method is applicable to represent extensible transformations for polymorphic variant data types in OCaml when other methods fail to do it. The method is not bound to any particular domain. It allows the creation of extensible transformations in OCaml. It could be ported to other functional languages supporting object-oriented programming.

1. Gibbons J. Datatype-generic programming. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 2007, vol. 4719, pp. 1–71. https://doi.org/10.1007/978-3-540-76786-2_1

2. Pottier F. Visitors unchained. Proceedings of the ACM on Programming Languages, 2017, vol. 1, pp. 1–28. https://doi.org/10.1145/3110272

3. Meijer E., Fokkinga M., Paterson R. Functional programming with bananas, lenses, envelopes and barbed wire. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1991, vol. 523, pp. 124–144. https://doi.org/10.1007/3540543961_7

4. Knuth D.E. Semantics of context-free languages. Mathematical Systems Theory, 1968, vol. 2, no. 2, pp. 127–145. https://doi.org/10.1007/BF01692511

5. Rendel T., Brachthauser J.I., Ostermann K. From object algebras to attribute grammars. ACM SIGPLAN Notices, 2014, vol. 49, no. 10, pp. 377–395. https://doi.org/10.1145/2714064.2660237

6. Viera M., Swierstra S.D., Swierstra W. Attribute grammars fly first-class: how to do aspect oriented  programming in Haskell. ACM SIGPLAN Notices, 2009, vol. 44, no. 9, pp. 245–256. https://doi.org/10.1145/1631687.1596586

7. Garrigue J. Programming with Polymorphic Variants. Conference ACM SIGPLAN Workshop on ML, 1998.

8. Garrigue J. Code reuse through polymorphic variants. Proc. Workshop on Foundations of Software Engineering, 2000.

9. Jones S.P., Vytiniotis D., Weirich S., Washburn G. Simple unification-based type inference for GADTs. ACM SIGPLAN Notices, 2006, vol. 41, no. 9, pp. 50–61. https://doi.org/10.1145/1160074.1159811

10. Kosarev D., Boulytchev D. Typed embedding of a relational language in OCaml. Electronic Proceedings in Theoretical Computer Science, EPTCS, 2018, vol. 285, pp. 1–22. https://doi.org/10.4204/eptcs.285.1

11. Wadler P. The Expression Problem. Available at: https://homepages.inf.ed.ac.uk/wadler/papers/expression/expression.txt (accessed: 26.07.2021).

12. Yallop J. Staged generic programming. Proc. of the ACM on Programming Languages, 2017, vol. 1, pp. 1–29. https://doi.org/10.1145/3110273

13. Lämmel R., Jones S.P. Scrap your boilerplate: A practical design pattern for generic programming. ACM SIGPLAN Notices, 2003, vol. 38, no. 3, pp. 26–37. https://doi.org/10.1145/640136.604179

14. Lämmel R., Jones S.P. Scrap more boilerplate: Reflection, zips, and generalised casts. ACM SIGPLAN Notices, 2004, vol. 39, no. 9, pp. 244–255. https://doi.org/10.1145/1016850.1016883

15. Boulytchev D., Mechtaev S. Efficiently Scrapping Boilerplate Code in OCaml. Workshop on ML, 2011.

This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License